package offer2

import (
	"fmt"
	"strconv"
	"strings"
)

/*
*
原题链接:
https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/

B站 帅地玩编程
剑指offer 37.序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。
你可以序列化如下的二叉树
8
/ \
12  2
/ \
6   4

为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"
*/

func Serialize(root *TreeNode) string {
	if root == nil { //如果跟节点为空, 直接返回""
		return ""
	}

	var result []string        //结果字符串集合
	queue := []*TreeNode{root} //放入队列

	for len(queue) > 0 { //只要队列有元素, 持续遍历
		node := queue[0] //取出节点
		queue = queue[1:]

		if node != nil { //如果节点不为空, 将节点值加入结果数组
			result = append(result, fmt.Sprintf("%d", node.Val))
			queue = append(queue, node.Left, node.Right) //当前节点的左右节点入队列
		} else { //如果当前节点为nil, 添加null到队列中
			result = append(result, "null")
		}
	}

	//返回结果字符串
	return strings.Join(result, ",")
}

func Deserialize(data string) *TreeNode {
	if data == "" { //如果string为"", 直接返回nil
		return nil
	}

	values := strings.Split(data, ",")    //以,分割 获取元素
	var queue []*TreeNode                 //节点队列
	rootVal, _ := strconv.Atoi(values[0]) //获取根节点值
	root := &TreeNode{Val: rootVal}       //创建根节点
	queue = append(queue, root)           //根节点入队列

	i := 1               //从根节点下一个位置开始
	for len(queue) > 0 { //只要队列有元素
		node := queue[0] //取出元素
		queue = queue[1:]

		if values[i] != "null" { //左节点  如果不是nil, 创建节点
			v, _ := strconv.Atoi(values[i])
			left := &TreeNode{Val: v}
			node.Left = left
			queue = append(queue, left)
		}
		i++

		if values[i] != "null" { //右节点  如果不是nil, 创建节点
			v, _ := strconv.Atoi(values[i])
			right := &TreeNode{Val: v}
			node.Right = right
			queue = append(queue, right)
		}
		i++
	}

	return root
}
